package code1_100.code30_40;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，
 * 还有一个 random 指针指向链表中的任意节点或者 null。
 *
 * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
 *
 * 输入：head = [[1,1],[2,1]]
 * 输出：[[1,1],[2,1]]
 *
 * 输入：head = [[3,null],[3,0],[3,null]]
 * 输出：[[3,null],[3,0],[3,null]]
 *
 * 输入：head = []
 * 输出：[]
 * 解释：给定的链表为空（空指针），因此返回 null。
 */
public class _35copyRandomList {


    Map<Node,Node> map = new HashMap<>();
    /**
     * 思考，头插法的变种，先试一下头插法。
     * 进一步思考，简单的循环复制行不通，因为当前节点的random节点无法确定。故需要考虑回溯的方法，
     * 如果random节点没创建，则递归进行创建。
     *
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
     * 内存消耗：38.2 MB, 在所有 Java 提交中击败了45.71% 的用户
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        if(head==null)return null;
        if(!map.containsKey(head)){
            Node newHead = new Node(head.val);
            map.put(head,newHead);
            newHead.next = copyRandomList(head.next);
            newHead.random = copyRandomList(head.random);
        }
        return map.get(head);
    }

    public Node copyRandomList2(Node head) {
        if(head==null) return null;
        ArrayList<Node> list = new ArrayList<>();
        while(head!=null){
            list.add(head);
            head = head.next;
        }

        //创建结果集合并初始化
        ArrayList<Node> res = new ArrayList<>();
        for(int i = 0;i<list.size();++i){
            res.add(new Node(list.get(i).val));
        }
        //设置结果结合的 random和next
        for (int i = 0; i < list.size(); ++i) {
            res.get(i).random = list.get(i).random == null?null:res.get(list.indexOf(list.get(i).random));
            if(i!=list.size()-1) res.get(i).next = res.get(i+1);
        }

        return res.get(0);
    }

}
